import java.util.Arrays;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-09-18
 * Time: 14:30
 */
public class experiment {
    public static void swap(int[] array,int m,int n){
        int tmp=array[m];
        array[m]=array[n];
        array[n]=tmp;
    }

    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    //这个是冒泡排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean isChange=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j+1,j);
                    isChange=true;
                }
            }
            if(!isChange){
                break;
            }
        }
    }


    //这里包括下面两段是堆排序
    public static void createBigHeap(int[] array){
        int parent=array.length-1-1/2;
        for (int i = parent; i >= 0; i--) {
            siftDown(array,i,array.length);
        }
    }

    public static void siftDown(int[] array,int parent,int end){
        int child=2*parent+1;
        while(child < end){
            if(child+1 < end && array[child] < array[child+1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    //时间复杂度：O(N^logN)
    //空间复杂度：O(1)
    public static void heapSort(int[] array){
        int end= array.length-1;
        createBigHeap(array);
        while(end > 0){
            swap(array,0,end);
            siftDown(array,0,end);
        }
    }

    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    //这是插入排序
    public static void insertSort(int[] array){
        for (int i = 1; i <= array.length-1; i++) {
            int tmp=array[i];//tmp可以被理解为被插入的那张卡牌
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp){
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    //这是选择排序，下面那个是另一个写法
    public static void selectSort1(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[minIndex] > array[j]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    public static void selectSort2(int[] array){
        int left=0;
        int right= array.length-1;
        for (int i = left; i < right; i++) {
            int minIndex=left;
            int maxIndex=left;
            for (int j = i+1; j <= right; j++) {
                if(array[j] > array[maxIndex]){
                    maxIndex=j;
                }
                if(array[j] < array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,maxIndex,right);
            swap(array,minIndex,left);
            right--;
        }
    }



    //这是统计数据问题，包括下面那段
    public static int[] divideNum(int num){
        int tmp=num;
        int count=0;
        while(tmp!=0){
            tmp=tmp/10;
            count++;
        }
        int[] array=new int[count];
        for (int i = 0; i < count; i++) {
            int x=num%10;
            num=num/10;
            array[i]=x;
        }
        return array;
    }

    public static int[] statisticNum(int n){
        int[] count=new int[10];
        for (int num = 1; num <= n; num++) {
            int[] array=divideNum(num);
            for (int i = 0; i < array.length; i++) {
                count[array[i]]++;
            }
        }
        return count;
    }


    //这是字典序问题
    public static void lexicographicalOrder(){
        HashMap<String,Integer> hashMap=new HashMap<>();
        hashMap.put("a",1);
        hashMap.put("b",2);
        hashMap.put("c",3);
        //以此类推...
    }


    public static void main(String[] args) {
        int[] count=statisticNum(20);
        System.out.println(Arrays.toString(count));
//        int[] array={1,4,2,6,3,9};
//        System.out.println("排序前："+Arrays.toString(array));
//        bubbleSort(array);
//        System.out.println("排序后："+Arrays.toString(array));
    }
}

















